[洛谷P1049]装箱问题

发表于 | 分类于 ， | | 阅读次数:

题目

题目描述

有一个箱子容量为 V （正整数，$ 0 <= V <=20000 $），同时有 n 个物品（ $ 0<n<=30 $ ，每个物品有一个体积（正整数）。

要求 nn 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
注：此问题区分大小写

输入格式

1 个整数，表示箱子容量

1 个整数，表示有 n 个物品

接下来 n 行，分别表示这 n 个物品的各自体积

输出格式

1个整数，表示箱子剩余空间。

样例输入

1
2
3
4
5
6
7
8
24
6
8
3
12
7
9
7

样例输出

1
0

来源

NOIp2001普及组 第4题

题解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
using namespace std;
int n,v;
int w[31];
int f[20001];

int main(){
	scanf("%d%d",&v,&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=v;j>=w[i];j--){
			f[j]=max(f[j],f[j-w[i]]+w[i]);
		}
	}
	printf("%d",v-f[v]);
	return 0;
}